package main

import (
	"strconv"
	"strings"
)

// 给定字符串，返回所有可能的有效ip
// 四个整数，每个整数位于0-255

// 搜索

func restoreIpAddresses(s string) []string {
	var res []string

	var search func(s string, path []string, startIdx int)
	search = func(s string, path []string, startIdx int) {
		// 终止条件
		if len(path) == 4 {
			// 得到一个结果
			tmpString := strings.Join(path, ".")
			res = append(res, tmpString)
		}
		// 当前层搜索
		for i := startIdx; i < len(s); i++ {
			// 得到一个合理的值
			path = append(path, s[startIdx:i+1])
			// 试探
			if i-startIdx+1 <= 3 && len(path) <= 4 && isValidIP(s, startIdx, i) {
				// 递归
				search(s, path, i+1)
			} else {
				return
			}
			// back
			path = path[:len(path)-1]
		}
	}
	search(s, []string{}, 0)
	return res
}

func isValidIP(s string, startIdx, endIdx int) bool {
	checkInt, _ := strconv.Atoi(s[startIdx : endIdx+1])
	if endIdx-startIdx+1 > 1 && s[startIdx] == '0' {
		return false // 前导0
	}
	if checkInt > 255 {
		return false
	}
	return true
}
